#include<bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while(ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while(ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while(x);
	while (__top) putchar(__stk[__top--] + '0');
}
bool stmer;
const int N = 1e5 + 10, mod = 1e9 + 7;
void add(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = 1ll * x * y % mod; }
struct node {
    int to, x;
    node operator + (const node &p) const {
        return {p.to, (x + p.x) % mod};
    }
} p[N][2], tmp[N];
int n, m, q;
int nex[N];
char s[N];
struct matrix {
    int a[4][4];
    void init() {
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++) a[i][j] = 0;
    }
    matrix operator * (const matrix &p) const {
        matrix tmp;
        for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) {
            tmp.a[i][j] = 0;
            for(int k = 0; k < 4; k++) add(tmp.a[i][j], 1ll * a[i][k] * p.a[k][j] % mod);
        }
        return tmp;
    }
} E, S, T;
matrix q_pow(matrix x, int k) {
    matrix res = E;
    for(; k; k >>= 1, x = x * x)
        if(k & 1) res = res * x;
    return res;
}
void init() {
    for(int i = 0; i < 4; i++) E.a[i][i] = 1;
    T.a[0][0] = T.a[1][3] = T.a[2][0] = T.a[2][1] = T.a[2][3] = T.a[3][1] = T.a[3][2] = 1;
}
void solve() {
    int fail = 0;
    p[0][s[1] - '0'] = {1, 0};
    if(m == 1) p[0][s[1] - '0'] = {0, 1};
    p[0][(s[1] - '0') ^ 1] = {0, 0};
    for(int i = 1; i < m; i++) {
        int op = s[i + 1] - '0';
        p[i][op] = {i + 1, 0};
        p[i][!op] = p[fail][!op];
        fail = p[fail][op].to;
        if(i + 1 == m) p[i][op] = {fail, 1};
    }
    int x = -1, y = -1;
    for(int i = 3; i <= n; i++) {
        // cout << p[0][1].to << " " << p[p[0][1].to][0].to << " ";
        for(int j = 0; j < m; j++) tmp[j] = p[j][1] + p[p[j][1].to][0];
        for(int j = 0; j < m; j++) swap(tmp[j], p[j][1]), swap(tmp[j], p[j][0]);
        if(x == p[0][1].to and y == p[0][0].to and i >= 50) {
            S.init();
            S.a[0][0] = p[0][1].x, S.a[0][1] = p[x][1].x;
            S.a[0][2] = p[x][0].x, S.a[0][3] = p[y][1].x;
            S = S * q_pow(T, n - i), p[0][1].x = S.a[0][0];
            break;
            // S.a00 = p[0][1].x, S.a01 = p[0][0].x, S.a10 = S.a11 = 0;
            // S = S * q_pow(T, n - i), p[0][1].x = S.a00; break;
        }
        else x = p[0][0].to, y = p[0][1].to;
    }
    if(n == 1) write(p[0][0].x);
    else write(p[0][1].x); putchar('\n');
}
bool edmer;
signed main() {
	freopen("brotherhood.in", "r", stdin);
	freopen("brotherhood.out", "w", stdout);
	// cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
    n = read(), q = read(), init();
    for(int i = 1; i <= q; i++) {
        scanf("%s", s + 1), m = strlen(s + 1);
        solve();
    }
    // cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds";
	return 0;
} 